import java.awt.Color;
import java.awt.Dimension;
import java.awt.FontMetrics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.geom.Point2D.Float;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// RedBlackTree class
//
// CONSTRUCTION: with no parameters
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x (unimplemented)
// Comparable find( x )   --> Return item that matches x
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print all items
// ******************ERRORS********************************
// Exceptions are thrown by insert if warranted and remove.

/**
 * Implements a red-black tree. Note that all "matching" is based on the
 * compareTo method. See delete implementations at the bottom!( some work and some don't)
 * 
 * @author Mark Allen Weiss & RebBlackTree Team
 */
public class RedBlackTree<AnyType extends Comparable<? super AnyType>>
												implements TreeInf<AnyType> {

	/**
	 * 4-14-2012 simeon gbolo added nodeLocations = new HashMap(); subtreeSizes
	 * = new HashMap(); Construct the tree.
	 */
	public RedBlackTree()
	{
		nullNode = new RedBlackNode<AnyType>(null);
		nullNode.left = nullNode.right = nullNode;
		header = new RedBlackNode<AnyType>(null);
		header.left = header.right = nullNode;
		nodeLocations = new HashMap<RedBlackNode<AnyType>, Rectangle>();
		subtreeSizes = new HashMap<RedBlackNode<AnyType>, Dimension>();
	}

	/**
	 * Simeon Gbolo added traversalPath, and outPut fields to show the user
	 * after a tree transformation Insert into the tree.
	 * 
	 * @param item
	 *            the item to insert.
	 * @throws DuplicateItemException
	 *             if item is already present.
	 */
	public void insert(AnyType item)
	{
		//Just keeps an integer reference to all the nodes
		// as they are inserted, this is an ordered list
		nodeList.add(Integer.parseInt(item.toString()));
		// used to store the traversal path of a
		// redBlacknode down a tree
		String traversalPath = "\nTaversed from ";
		output = "";
		current = parent = grand = header;
		nullNode.element = item;

		while (compare(item, current) != 0)
		{
			great = grand;
			grand = parent;
			parent = current;
			current = compare(item, current) < 0 ? current.left : current.right;

			// Check if two red children; fix if so
			if (current.left.getColorChangeHelper() == RED
					&& current.right.getColorChangeHelper() == RED)
			{
				handleReorient(item);
			}
			traversalPath += "  " + current.getElement().toString() + ", ";
		}

		// Insertion fails if already present
		if (current != nullNode)
			// The thrown exception below is absent right now, so temp code
			// follows - Rob Mann
			// throw new DuplicateItemException( item.toString( ) );
			System.out.println("Node already exists!"); // added - Rob Mann
		current = new RedBlackNode<AnyType>(item, nullNode, nullNode);
		size++;
		current.parent = parent;
		// Attach to parent
		if (compare(item, parent) < 0)
			parent.left = current;
		else
			parent.right = current;
		handleReorient(item);
	}

	/**
	 * Find the smallest item the tree.
	 * 
	 * @return the smallest item or null if empty.
	 */
	public AnyType findMin()
	{
		if (isEmpty())
			return null;

		RedBlackNode<AnyType> itr = header.right;

		while (itr.left != nullNode)
			itr = itr.left;

		return itr.element;
	}

	/**
	 * Find the smallest item the tree.
	 * 
	 * @return the smallest item or null if empty.
	 */
	public RedBlackNode<AnyType> findMinNode(RedBlackNode<AnyType> itr)
	{
		if (isEmpty())
			return null;

		while (itr.left != nullNode)
			itr = itr.left;

		return itr;
	}

	/**
	 * Find the largest item in the tree.
	 * 
	 * @return the largest item or null if empty.
	 */
	public AnyType findMax()
	{
		if (isEmpty())
			return null;

		RedBlackNode<AnyType> itr = header.right;

		while (itr.right != nullNode)
			itr = itr.right;

		return itr.element;
	}

	/**
	 * Find an item in the tree.
	 * 
	 * @param x
	 *            the item to search for.
	 * @return the matching item or null if not found.
	 */
	public boolean search(AnyType x)
	{
		nullNode.element = x;
		current = header.right;

		for (;;)
		{
			if (x.compareTo(current.element) < 0)
				current = current.left;
			else
				if (x.compareTo(current.element) > 0)
					current = current.right;
				else
					if (current != nullNode)
					{
						current.setFound(true);
						return true;
					} else
						return false;
		}
	}

	/**
	 * Finds a node in the tree and returns a refrence to the node
	 * @param x
	 * @return
	 */
	public RedBlackNode<AnyType> findNode(AnyType x)
	{
		nullNode.element = x;
		current = header.right;

		for (;;)
		{
			if (x.compareTo(current.element) < 0)
				current = current.left;
			else
				if (x.compareTo(current.element) > 0)
					current = current.right;
				else
					if (current != nullNode)
					{

						return current;
					} else
						return null;
		}
	}

	/**
	 * Make the tree logically empty.
	 */
	public void clear()
	{
		header.right = nullNode;
		size = 0;
	}

	/**
	 * 2004 * Returns the predecessor of the specified Entry, or null if no
	 * such. 2005
	 */
	public RedBlackNode<AnyType> predecessor(RedBlackNode<AnyType> t)
	{
		if (t == nullNode)
			return nullNode;
		else
			if (t.left != nullNode)
			{
				RedBlackNode<AnyType> p = t.left;
				while (p.right != nullNode)
					p = p.right;
				return p;
			} else
			{
				RedBlackNode<AnyType> p = t.parent;
				RedBlackNode<AnyType> ch = t;
				while (p != nullNode && ch == p.left)
				{
					ch = p;
					p = p.parent;
				}
				return p;
			}
	}

	/**
	 * Print all items.
	 */
	public void printTree()
	{
		printTree(header.right);
	}



	/**
	 * Evaluates an entire RedBlackTree to determine height. 1) Nil nodes are
	 * not irrelevant. 2) If head == NullNode, returns -1 3) Dependent on the
	 * following methods: public int getDepth() private int
	 * depthHelper(RedBlackNode<AnyType> t) Added 2012-04-13: Rob Mann
	 */
	public int getHeight()
	{
		// Since Height of tree and Depth are same
		return -1 + depthHelper(this.header);
	}



	/**
	 * Evaluates an entire RedBlackTree to determine depth. 1) Nil nodes are not
	 * irrelevant. 2) If head == NullNode, returns -1 3) Dependent on the
	 * following helper method: private int depthHelper(RedBlackNode<AnyType> t)
	 * Added 2012-04-13: Rob Mann
	 */
	public int getDepth()
	{
		return -1 + depthHelper(this.header);
	}


	/**
	 * Analyzes the tree and returns average depth of all nodes in tree.
	 * Returns -1 if empty tree.
	 * Returns 0 if root only.
	 * Since this returns an int, any tree with 1,2,or 3 nodes has average depth = 0,
	 * and as far as I have been able to find there is no correct way to interpret 
	 * converting this to an int. double would seem more natural IMHO.
	 *  
	 * This function looks at the tree and reports exactly as it sees it,
	 * even if RTB rules are violated. 
	 * 
	 * -Rob Mann
	 */
	public double getAverageDepth() {
		if (this.header.right == nullNode){
			return -1;
		} else{ 
			//System.out.println("Sum of depths is "+sumDepths(this.header.right,-1));
			return (double)(sumDepths(this.header.right,-1))/size;
		}
	}
	
	/**
	 * Mostly acts as a helper for getAverageDepth
	 * Returns the total depths of all nodes below a given node and
	 * a start depth (usually -1, for depth with no nodes). Scope is private,
	 * but could be widened.
	 * -Rob Mann
	 */
	private int sumDepths(RedBlackNode<AnyType> t, int depth) {
		if (t != nullNode) {
			depth++;
			// System.out.println("Node is "+t.getElement()+
			// "   L="+t.getLeft().getElement()+"   R="+t.getRight().getElement());
			
			//return depth + sumDepths(t.getLeft(),depth) + sumDepths(t.getRight(),depth);
			System.out.println(depth+" "+sumDepths(t.getLeft(),depth)+" "+sumDepths(t.getRight(),depth));
			return depth + sumDepths(t.getLeft(),depth) + sumDepths(t.getRight(),depth);
		} else{
			return 0; // done looking
		}
	}
	
	/**
	 * Analyzes tree for actual size, regardless of accounting for
	 * size field. Should not bee needed if accounting of size field is correct.
	 * -Rob Mann
	 */
	public int calcSize() {
		return calcSizeHelper(header.right);
	}
	
	/**
	 * helper for calcSize()
	 * Scope is private, but could be widened.
	 * -Rob Mann
	 */
	private int calcSizeHelper(RedBlackNode<AnyType> t) {
		if (t != nullNode) {
			return 1 + calcSizeHelper(t.getLeft()) + calcSizeHelper(t.getRight());
		} else{
			return 0; // done looking
		}
	}
	
	/**
	 * Returns the size, in number of nodes, of the tree.
	 * -Rob Mann
	 */
	public int getSize() {
		/* If size accounting has been implemented (ie. size++ for insertions,
		* size-- for deletions, and seize = 0 for clear tree), simply return size,
		* otherwise, calcSize is available and works by analyzing the entire tree 
		* for actual size. Ugly, but works if we missed accounting.
		*/
		
		//return size;
		
		return this.calcSize();
	}
	
/**
	 * Test if the tree is logically empty.
	 * 
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty()
	{
		return header.right == nullNode;
	}

	/**
	 * @author Simeon Gbolo the tree tells all the nodes to update themselves
	 *         Depending on their states (helper method)
	 * @param n
	 *            the root
	 * @param deltaTime
	 *            delta time
	 */
	public void update(float deltaTime)
	{

		// takes the root and the delta time
		update(header.right, deltaTime);
		
		if(nodeToBeDeleted != null){
			nodeToBeDeleted.advance(deltaTime);
			if( nodeToBeDeleted.state == RedBlackNode.RedBlackNodeState.paused){
				nodeToBeDeleted = null;
			}
		}

	}

	/**
	 * @author Simeon Gbolo public helper method that draws the current states
	 *         of the nodes on the canvas
	 * @param g2
	 */
	public void drawStates(Graphics2D g2)
	{

		drawStates(g2, header.getRight(), Integer.MAX_VALUE, Integer.MAX_VALUE);

	}

	/**
	 * 4-14-2012
	 * 
	 * @author simeon Gbolo After inserting a node, search for it to find the
	 *         path This path of points are use for animating a node down the
	 *         tree This feature may not be implemented as the current version
	 *         looks pretty good IMO(in my opinion)
	 * @param x
	 *            the item to find a path to
	 * @return the Queue path for a RedBlackNode after insertion
	 */
	public boolean setPath(AnyType x)
	{
		Queue<Float> path = new LinkedList<Float>();

		nullNode.element = x;
		current = header.right;

		for (;;)
		{
			if (x.compareTo(current.element) < 0)
			{
				path.add(current.getCurrentXYlocation());
				current = current.left;
			} else
				if (x.compareTo(current.element) > 0)
				{
					path.add(current.getCurrentXYlocation());
					current = current.right;
				} else
					if (current != nullNode)
					{
						current.setPath(path);
						return true;// path was set
					} else
					{
						// if path is false then this is the root
						return false;
					}
		}

	}

	/**
	 * @author Simeon Gbolo calculate node destinations by calculating the size
	 *         of the subtrees and then add the destinations to the
	 *         nodes(recursively)
	 * @param fontMetrics
	 * 
	 */
	public void calculateNodeDestinations(FontMetrics fontMetrics)
	{
		fm = fontMetrics;
		// clear node loactions
		nodeLocations.clear();
		// clear sub tree sizes
		subtreeSizes.clear();
		if (header.right != nullNode)
		{
			calculateSubtreeSize(header.right);
			calculateDestination(header.right, Integer.MAX_VALUE,
					Integer.MAX_VALUE, 0);

		}

	}

	
	/**
	 * returns a string representation of statistics on the tree.
	 * -Rob Mann
	 */
	@Override
	public String toString(){
		return "tree size = "+this.getSize()+" , tree height = "+this.getHeight()+" , average depth = "+this.getAverageDepth();
	}

	private RedBlackNode<AnyType> rightOf(RedBlackNode<AnyType> x)
	{
		// TODO Auto-generated method stub
		return x.right;
	}

	private RedBlackNode<AnyType> leftOf(RedBlackNode<AnyType> x)
	{
		// TODO Auto-generated method stub
		return x.left;
	}

	private RedBlackNode<AnyType> parentOf(RedBlackNode<AnyType> x)
	{
		// TODO Auto-generated method stub
		return x.parent;
	}

	/**
	 * 1982 * Returns the successor of the specified Entry, or null if no such.
	 * 1983
	 */
	private RedBlackNode<AnyType> successor(RedBlackNode<AnyType> t)
	{
		if (t == nullNode)
			return nullNode;
		else
			if (t.right != nullNode)
			{
				RedBlackNode<AnyType> p = t.right;
				while (p.left != nullNode)
					p = p.left;
				return p;
			} else
			{
				RedBlackNode<AnyType> p = t.parent;
				RedBlackNode<AnyType> ch = t;
				while (p != nullNode && ch == p.right)
				{
					ch = p;
					p = p.parent;
				}
				return p;
			}
	}

	/**
	 * Compare item and t.element, using compareTo, with caveat that if t is
	 * header, then item is always larger. This routine is called if is possible
	 * that t is header. If it is not possible for t to be header, use compareTo
	 * directly.
	 */
	private final int compare(AnyType item, RedBlackNode<AnyType> t)
	{
		if (t == header)
			return 1;
		else
			return item.compareTo(t.element);
	}

	/**
	 * Internal method to print a subtree in sorted order.
	 * 
	 * @param t
	 *            the node that roots the tree.
	 */
	private void printTree(RedBlackNode<AnyType> t)
	{
		if (t != nullNode)
		{
			printTree(t.left);
			System.out.println(t.element);
			printTree(t.right);
		}
	}



	/**
	 * Helper method for - public int getDepth() 1) Nil nodes are not
	 * irrelevant. 2) If head == NullNode, returns -1 3) Dependent on the
	 * following helper method: private int depthHelper(RedBlackNode<AnyType> t)
	 * Added 2012-04-13: Rob Mann
	 */
	private int depthHelper(RedBlackNode<AnyType> t)
	{
		int depth = -1;
		if (t != nullNode)
		{
			// System.out.println("Node is "+t.getElement()+
			// "   L="+t.getLeft().getElement()+"   R="+t.getRight().getElement());
			depth = 1 + Math.max(depthHelper(t.getLeft()),
					depthHelper(t.getRight()));
		}
		return depth; // done looking
	}

	/**
	 * Internal routine that is called during an insertion if a node has two red
	 * children. Performs flip and rotations.
	 * 
	 * @param item
	 *            the item being inserted.
	 */
	private void handleReorient(AnyType item)
	{
		// Do the color flip
		current.setColor(RED);
		current.left.setColor(BLACK);
		current.right.setColor(BLACK);

		if (parent.getColorChangeHelper() == RED) // Have to rotate
		{
			grand.setColor(RED);
			if ((compare(item, grand) < 0) != (compare(item, parent) < 0))
				parent = rotate(item, grand); // Start dbl rotate
			current = rotate(item, great);
			current.setColor(BLACK);
		}
		header.right.setColor(BLACK); // Make root black
	}

	/**
	 * Internal routine that performs a single or double rotation. Because the
	 * result is attached to the parent, there are four cases. Called by
	 * handleReorient.
	 * 
	 * @param item
	 *            the item in handleReorient.
	 * @param parent
	 *            the parent of the root of the rotated subtree.
	 * @return the root of the rotated subtree.
	 */
	private RedBlackNode<AnyType> rotate(AnyType item,
			RedBlackNode<AnyType> parent)
	{
		if (compare(item, parent) < 0)
			return parent.left = compare(item, parent.left) < 0 ? rotateWithLeftChild(parent.left)
					: // LL
					rotateWithRightChild(parent.left); // LR
		else
			return parent.right = compare(item, parent.right) < 0 ? rotateWithLeftChild(parent.right)
					: // RL
					rotateWithRightChild(parent.right); // RR
	}

	/**
	 * Added output strings for rotations, may need to be fixed with larger
	 * rotations(simeon gbolo) Rotate binary tree node with left child.
	 */
	private static <AnyType> RedBlackNode<AnyType> rotateWithLeftChild(
			RedBlackNode<AnyType> b)
	{

		output += "------------\n Rotated " + b.element.toString() +"" +
				" with it's left child";
		
		RedBlackNode<AnyType> pA, pB, pBeta;
		pA = b.parent;
		pB = b.left;
		pBeta = b;

		
		RedBlackNode<AnyType> a = b.left;
		a.right.parent = pBeta;

		b.parent = pB;
		b.left = a.right;

		a.parent = pA;
		a.right = b;

		return a;
	}

	/**
	 * Rotate binary tree node with right child.
	 */
	private static <AnyType> RedBlackNode<AnyType> rotateWithRightChild(
			RedBlackNode<AnyType> a)
	{
		
		output += "------------\n Rotated " + a.element.toString() +"" +
		" with it's right child";

		RedBlackNode<AnyType> pA, pB, pBeta;
		pA = a.right;
		pB = a.parent;
		pBeta = a;

	
		RedBlackNode<AnyType> b = a.right;
		b.left.parent = pBeta;

		a.parent = pA;
		a.right = b.left;

		b.parent = pB;
		b.left = a;


		return b;
	}

	/**
	 * @author Simeon Gbolo Private recursive method to have all the nodes in
	 *         the tree update themselves(advance)
	 * @param t
	 * @param deltaTime
	 */
	private void update(RedBlackNode<AnyType> t, float deltaTime)
	{
		if (t != nullNode)
		{
			update(t.left, deltaTime);
			t.advance(deltaTime);
			update(t.right, deltaTime);
		}

	}

	/**
	 * @author simeon Gbolo Recursively draw the states of each node, their
	 *         color and the nullNodes
	 * @param g
	 *            the graphics object used to draw with
	 * 
	 * @param n
	 *            the current node being drawn
	 * @param px
	 *            x coordinate of line to draw
	 * @param py
	 *            y coordinate of line to draw
	 * 
	 */
	private void drawStates(Graphics2D g, RedBlackNode<AnyType> n, int px,
			int py)
	{
		
		if(nodeToBeDeleted != null){
			g.setColor(Color.green);
			g.fillOval((int) nodeToBeDeleted.getX(), (int) nodeToBeDeleted.getY() , 20, 20);
			g.setColor(Color.black);
			
			if (Integer.parseInt(nodeToBeDeleted.getElement().toString()) > 9)
			{
				g.drawString(nodeToBeDeleted.element.toString(),
						((int) nodeToBeDeleted.getX() + fm.getAscent() / 2) - 4,
						(int) nodeToBeDeleted.getY() + fm.getAscent());
			} else
			{
				g.drawString(nodeToBeDeleted.element.toString(),
						((int) nodeToBeDeleted.getX() + fm.getAscent() / 2), (int) nodeToBeDeleted.getY()
								+ fm.getAscent());
			}
		}

		if (n != nullNode)
		{
			// set color to red
			g.setColor(Color.red);

			// get the locations of n according to the precalulated locations
			Rectangle r = (Rectangle) nodeLocations.get(n);

			// if the node is being searched for
			// paint it yellow
			if (n.isFound())
			{
				g.setColor(Color.YELLOW);
			} else
			{
				color = new Color((int) n.getRedHue(), 0, 0);
				g.setColor(color);
			}
			g.fillOval((int) n.getX(), (int) n.getY(), 20, 20);

			// draw the small nullNode if they exist
			if (n.getLeft() == nullNode)
			{
				g.setColor(Color.black);
				g.fillOval((int) n.getX() - 3, (int) n.getY() + 18, 10, 10);
			}

			// draw the small nullNode if they exist
			if (n.getRight() == nullNode)
			{
				g.setColor(Color.black);
				g.fillOval((int) n.getX() + 13, (int) n.getY() + 18, 10, 10);
			}

			// Set String color to white if not found
			if (n.isFound())
			{
				g.setColor(Color.black);
			} else
			{
				g.setColor(Color.white);
			}

			// adjust the string to the middle of the circle
			if (Integer.parseInt(n.getElement().toString()) > 9)
			{
				g.drawString(n.element.toString(),
						((int) n.getX() + fm.getAscent() / 2) - 4,
						(int) n.getY() + fm.getAscent());
			} else
			{
				g.drawString(n.element.toString(),
						((int) n.getX() + fm.getAscent() / 2), (int) n.getY()
								+ fm.getAscent());
			}

			// draw the line
			g.setColor(Color.black);
			if (px != Integer.MAX_VALUE)
			{
				if (n.state == RedBlackNode.RedBlackNodeState.moving)
				{
					g.setColor(Color.BLUE);// we know the line is adjusting

				}
				g.drawLine(px + 3, py, n.getX() + 7, n.getY());
			}
			drawStates(g, n.getLeft(), r.x + r.width / 2, r.y + r.height);
			drawStates(g, n.getRight(), r.x + r.width / 2, r.y + r.height);

		}

	}

	/**
	 * @author Simeon gbolo 4-14-2012 Recursively calculate the destination of
	 *         each node and call setUpForNavigation(XyDest) on each node to
	 *         make it animate to the correct position
	 * @param n
	 * @param left
	 * @param right
	 * @param top
	 */
	private void calculateDestination(RedBlackNode<AnyType> n, int left,
			int right, int top)
	{
		if (n == nullNode)
			return;
		Dimension ld = (Dimension) subtreeSizes.get(n.getLeft());
		if (ld == null)
			ld = empty;
		Dimension rd = (Dimension) subtreeSizes.get(n.getRight());
		if (rd == null)
			rd = empty;
		int center = 0;
		if (right != Integer.MAX_VALUE)
			center = right - rd.width - child2child / 2;
		else
			if (left != Integer.MAX_VALUE)
				center = left + ld.width + child2child / 2;
		int width = fm.stringWidth(n.getElement().toString());

		// a rectangle for now - but really a circle
		Rectangle r = new Rectangle(center - width / 2 - 3, top, width + 6, 16);
		nodeLocations.put(n, r);
		Float xYDest = new Float();
		//
		xYDest.setLocation(r.getX(), r.getY());
		n.setUpForNavigation(xYDest);

		calculateDestination(n.left, Integer.MAX_VALUE, center - child2child
				/ 2, top + fm.getHeight() + parent2child);
		calculateDestination(n.right, center + child2child / 2,
				Integer.MAX_VALUE, top + fm.getHeight() + parent2child);
	}

	/**
	 * Recursively calculate the size subtrees rooted at N
	 * 
	 * @param n
	 * @return
	 */
	private Dimension calculateSubtreeSize(RedBlackNode<AnyType> n)
	{
		if (n == nullNode)
			return new Dimension(0, 0);
		n.getElement().toString();

		Dimension ld = calculateSubtreeSize(n.left);
		Dimension rd = calculateSubtreeSize(n.right);

		int h = fm.getHeight() + parent2child + Math.max(ld.height, rd.height);

		int w = ld.width + child2child + rd.width;
		Dimension d = new Dimension(w, h);
		subtreeSizes.put(n, d);
		return d;
	}

	/**
	 * Temporary delete method -in Testing
	 * @param n
	 * the node to delete
	 */
	public void RBdelete(RedBlackNode<AnyType> n)
	{

		RBdelete(nullNode, n);
	}

	/**
	 * Temporary delete method -in Testing
	 * @param sentinel - a null node
	 * @param z
	 */
	private void RBdelete(RedBlackNode<AnyType> sentinel,
			RedBlackNode<AnyType> z)
	{

		RedBlackNode<AnyType> y = z;

		int theOriginalColorOfY = y.color;

		if (z.left == nullNode)
		{
			transPlant(z, z.right);
		} else
			if (z.right == nullNode)
			{
				transPlant(z, z.left);
			} else
			{
				y = findMinNode(z.right);
				theOriginalColorOfY = y.color;
				RedBlackNode<AnyType> x = y.right;
				if (compare(y.parent.element, z) == 0)
				{
					x.parent = y;
				} else
				{
					transPlant(z, y);
					y.right = z.right;
					y.right.parent = y;
				}
				transPlant(z, y);
				y.left = z.left;
				y.left.parent = y;

				y.setColor(z.color);
				y.color = z.color;
				if (theOriginalColorOfY == BLACK)
				{
					RBDeleteFixup(x);
				}
			}

	}

	/**
	 * Temporary delete method -in Testing
	 * @param u
	 * @param v
	 */
	private void transPlant(RedBlackNode<AnyType> u, RedBlackNode<AnyType> v)
	{

		if (u.parent == nullNode)
		{// this is the root if true
			header.right = v;
		} else
			if (compare(u.element, u.parent) == 0)
			{
				u.parent.left = v;
			} else
			{
				u.parent.right = v;
			}

		v.parent = u.parent;
	}

	/**
	 * 2135 * Delete node p, and then rebalance the tree. 2136
	 */

	/**
	 * Temporary delete method -in Testing
	 * @param p
	 */
	public void delete(AnyType e)
	{
		// Added when updating method signature (TreeInf)
		RedBlackNode<AnyType> p = findNode(e);
		
		// modCount++;
		size--;

		// If strictly internal, copy successor's element to p and then make p
		// point to successor.
		if (p.left != nullNode && p.right != nullNode)
		{
			RedBlackNode<AnyType> s = successor(p);
			p.element = s.element;
			p = s;
		} // p has 2 children

		// Start fixup at replacement node, if it exists.
		RedBlackNode<AnyType> replacement = (p.left != nullNode ? p.left
				: p.right);

		if (replacement != nullNode)
		{
			// Link replacement to parent
			replacement.parent = p.parent;
			if (p.parent == nullNode)
				header.right = replacement;
			else
				if (p == p.parent.left)
					p.parent.left = replacement;
				else
					p.parent.right = replacement;

			// Null out links so they are OK to use by fixAfterDeletion.
			p.left = p.right = p.parent = nullNode;

			// Fix replacement
			if (p.color == BLACK)
				fixAfterDeletion(replacement);
		} else
			if (p.parent == nullNode)
			{ // return if we are the only node.
				header.right = nullNode;
			} else
			{ // No children. Use self as phantom replacement and unlink.
				if (p.color == BLACK)
					fixAfterDeletion(p);

				if (p.parent != nullNode)
				{
					if (p == p.parent.left)
						p.parent.left = nullNode;
					else
						if (p == p.parent.right)
							p.parent.right = nullNode;
					p.parent = nullNode;
				}
			}

	}

	/**
	 * Temporary delete helper method -in Testing
	 * @param x
	 */
	private void RBDeleteFixup(RedBlackNode<AnyType> x)
	{

		while (compare(x.element, header.right) != 0 && x.color == BLACK)
		{

			if (compare(x.element, x.parent.left) == 0)
			{
				RedBlackNode<AnyType> w = x.parent.right;
				if (w.color == RED)
				{
					w.setColor(BLACK);
					w.color = BLACK;

					x.parent.setColor(RED);
					x.parent.color = RED;
					rotateWithLeftChild(x.parent);
					w = x.parent.right;
				}
				if (w.left.color == BLACK && w.right.color == BLACK)
				{
					w.setColor(RED);
					w.color = RED;

					x = x.parent;
				} else
					if (w.right.color == BLACK)
					{
						w.left.setColor(BLACK);
						w.left.color = BLACK;

						w.setColor(RED);
						w.color = RED;

						rotateWithRightChild(w);
						w = x.parent.right;
					}

				w.setColor(x.parent.color);
				w.color = x.parent.color;

				x.parent.setColor(BLACK);
				x.parent.color = BLACK;

				w.right.setColor(BLACK);
				w.right.color = BLACK;

				rotateWithLeftChild(x.parent);

			}
			x = header.right;
		}
		x.setColor(BLACK);
		x.color = BLACK;

	}

	/** 
	/**Temporary delete helper method -in Testing
	 * @param x
	 */
	private void fixAfterDeletion(RedBlackNode<AnyType> x)
	{
		while (x != header.right && x.color == BLACK)
		{
			System.out.println("inside while");
			if (x == leftOf(parentOf(x)))
			{
				System.out.println("inside If - left of parent");
				RedBlackNode<AnyType> sib = rightOf(parentOf(x));

				if (sib.color == RED)
				{
					sib.setColor(BLACK);
					sib.color = BLACK;
					x.parent.setColor(RED);
					x.parent.color = RED;
					rotateWithLeftChild(parentOf(x));
					sib = rightOf(parentOf(x));
				}

				if ((leftOf(sib)).color == BLACK
						&& (rightOf(sib)).color == BLACK)
				{
					sib.setColor(RED);
					sib.color = RED;
					x = parentOf(x);
				} else
				{
					if ((rightOf(sib)).color == BLACK)
					{
						leftOf(sib).color = BLACK;
						sib.setColor(RED);
						sib.color = RED;
						rotateWithRightChild(sib);
						sib = rightOf(parentOf(x));
					}
					sib.setColor(parentOf(x).color);
					sib.color = (parentOf(x)).color;
					parentOf(x).setColor(BLACK);
					rightOf(sib).setColor(BLACK);
					rotateWithLeftChild(parentOf(x));
					x = header.right;
				}
			} else
			{ // symmetric
				RedBlackNode<AnyType> sib = leftOf(parentOf(x));

				if ((sib).color == RED)
				{
					sib.setColor(BLACK);
					sib.color = BLACK;
					parentOf(x).setColor(RED);
					parentOf(x).color = RED;
					rotateWithRightChild(parentOf(x));
					sib = leftOf(parentOf(x));
				}

				if ((rightOf(sib)).color == BLACK
						&& (leftOf(sib)).color == BLACK)
				{
					sib.setColor(RED);
					sib.color = RED;
					x = parentOf(x);
				} else
				{
					if ((leftOf(sib)).color == BLACK)
					{
						rightOf(sib).setColor(BLACK);
						rightOf(sib).color = BLACK;
						sib.setColor(BLACK);
						sib.color = BLACK;
						rotateWithLeftChild(sib);
						sib = leftOf(parentOf(x));
					}
					sib.setColor(parentOf(x).color);
					sib.color = (parentOf(x)).color;

					parentOf(x).setColor(BLACK);
					parentOf(x).color = BLACK;

					leftOf(sib).setColor(BLACK);
					leftOf(sib).color = BLACK;
					rotateWithRightChild(parentOf(x));
					x = header.right;
				}
			}
		}

		x.setColor(BLACK);
		x.color = BLACK;
	}
	
	/**
	 * This method is used to reset the tree and 
	 * and reinsert the requested node after deletion
	 * 
	 * @param x
	 */
	public void deleteReset(AnyType x){
		
		nodeToBeDeleted = findNode(x);
		for(int i = 0 ; i < nodeList.size() ; i ++){
			
			if(nodeList.get(i) == x){
				nodeList.remove(i);
				break;
			}
		}
		//nodeToBeDeleted.currentXYlocation = findNode(x).currentXYlocation;
		
		
		header.right = nullNode;
		size --;
		
		Object[] tmp =  nodeList.toArray();
		nodeList = new ArrayList<Integer>();
		
		for(int i = 0 ; i < tmp.length ; i ++){
			
			insert((AnyType) tmp[i]);
			
		}
		nodeToBeDeleted.setUpForNavigation(new Float(900, 900));
		
		
	}

	/**
	 * 
	 * @author RedBlackTree Team
	 * 
	 * @param <AnyType>
	 */
	private static class RedBlackNode<AnyType> {

		/**
		 * All the possible states of any RedBlackNode in a RedBlack Tree
		 * 
		 * @author Simeon Gbolo
		 * 
		 */
		enum RedBlackNodeState
		{
			moving, paused, changingColor
		}

		RedBlackNode<AnyType> parent;
		AnyType element; // The data in the node
		RedBlackNode<AnyType> left; // Left child
		RedBlackNode<AnyType> right; // Right child
		int color; // Color

		int colorChangeHelper; // used to chnage the color

		// true if the color needs to be changed afte
		// the node moves it's self
		// animation will happen accordinly
		boolean colorChangeFlag = false;

		boolean isFound = false;

		float foundCounter = 0;
		// the current location on the node in the x,y plane
		Float currentXYlocation;

		// the current destination of the node in the x,y plane
		Float currentXYdestination;

		Float startingPoint;

		// running time for this animation
		float runningTime;

		// used to calculate the slope for moving from one point to another
		float rise;

		// Used to calculate the slope for moving from one spot to another
		float run;

		// used to change from red to black
		float redHue;

		// a path for this node to follow
		Queue<Float> path;

		RedBlackNodeState state;

		// Constructors
		RedBlackNode(AnyType theElement)
		{
			this(theElement, null, null);
		}

		RedBlackNode(AnyType theElement, RedBlackNode<AnyType> lt,
				RedBlackNode<AnyType> rt)
		{
			element = theElement;
			left = lt;
			right = rt;
			color = RedBlackTree.RED;
			redHue = 255f;
			colorChangeHelper = RedBlackTree.BLACK;
			currentXYlocation = new Float();
			currentXYdestination = new Float();
			startingPoint = new Float();
			path = new LinkedList<Float>();
			runningTime = 0;
			state = RedBlackNodeState.paused;

		}

		/**
		 * @param isFound
		 *            the isFound to set
		 */
		public void setFound(boolean isFound)
		{
			this.isFound = isFound;
		}

		/**
		 * @return the isFound
		 */
		public boolean isFound()
		{
			return isFound;
		}

		/**
		 * @author simeon Gbolo Sets the color change helper to to the future
		 *         color if the node and sets the color flag to true so that we
		 *         know to change the state to changing color after the moving
		 *         state
		 * 
		 *         otherwise
		 * @param color
		 */
		public void setColor(int color)
		{
			if (this.color == color)
			{
				this.colorChangeHelper = color;
				return;
			} else
			{
				this.colorChangeHelper = color;
				colorChangeFlag = true;
			}
		}

		public float getRedHue()
		{
			return redHue;
		}

		public int getColorChangeHelper()
		{
			return colorChangeHelper;
		}

		// Added getElement() 2012-04-13 Rob Mann
		public AnyType getElement()
		{
			return element;
		}

		// Added getLeft() 2012-04-13 Rob Mann
		public RedBlackNode<AnyType> getLeft()
		{
			return left;
		}

		// Added getRight() 2012-04-13 Rob Mann
		public RedBlackNode<AnyType> getRight()
		{
			return right;
		}

		/**
		 * This method makes the node update it's self depending on it's current
		 * state
		 * 
		 * @param deltaTime
		 */
		public void advance(float deltaTime)
		{

			if (state == RedBlackNodeState.moving)
			{
				updateMoving(deltaTime);
			}

			if (state == RedBlackNodeState.paused)
			{
				updatePaused(deltaTime);
			}

			if (state == RedBlackNodeState.changingColor)
			{
				updateChangingColor(deltaTime);
			}
		}

		/**
		 * Used to do color fading animation when changing from red to black, if
		 * the color is changing to black decrease the red hue value otherwise
		 * if the color is changing to red , increase the red hue value
		 * 
		 * @param deltaTime
		 */
		private void updateChangingColor(float deltaTime)
		{

			if (color == RED)
			{
				if (redHue >= 255)
				{
					redHue = 255;
					state = RedBlackNodeState.paused;
				} else
					redHue += .5;
			}

			if (color == BLACK)
			{
				if (redHue <= 0)
				{
					redHue = 0;
					state = RedBlackNodeState.paused;
				} else
					redHue -= .5;

			}
			


		}

		/**
		 * @author Simeon Gbolo depending on what ever is first point in the
		 *         path queue, the node will travel to that location. once it
		 *         reaches that location and if the Queue is not empty - it will
		 *         move on to the next point in the queue
		 * 
		 * @param deltaTime
		 *            the change in time
		 */
		private void updateMoving(float deltaTime)
		{
			runningTime += deltaTime;

			float newX = (float) (startingPoint.getX() + run * runningTime);
			float newY = (float) (startingPoint.getY() + rise * runningTime);
			currentXYlocation.setLocation(newX, newY);
			// System.out.println("" +getDistanceFromDestination() );
			if (getDistanceFromDestination() <= 2)
			{
				if (!path.isEmpty())
				{
					setUpForNavigation(path.poll());
				} else
				{
					if (colorChangeFlag)
					{
						this.color = colorChangeHelper;
						colorChangeFlag = false;

						state = RedBlackNodeState.changingColor;

					} else
					{
						currentXYlocation.setLocation(currentXYdestination);
						state = RedBlackNodeState.paused;
					}
				}
			}

		}

		/**
		 * @author Simeon gbolo set running time to 0 and if the node is found
		 *         while paused add .5 to node counder until it reaches 1000 -
		 *         then the node will be back it's original color
		 * 
		 * @param deltaTime
		 */
		private void updatePaused(float deltaTime)
		{
			runningTime = 0;
			if (isFound)
			{
				foundCounter += .5;
			}

			if (foundCounter > 1000)
			{
				isFound = false;
				foundCounter = 0;
			}

			if (colorChangeFlag)
			{
				
				state = RedBlackNodeState.changingColor;
			}
			
			
		}

		/**
		 * @author Simeon Gbolo This method is used to calculate the distance
		 *         from one point to another. 04-14-2012
		 * @return The distance from one point to another
		 */
		public int getDistanceFromDestination()
		{

			return (int) currentXYlocation.distance(currentXYdestination);
		}

		/**
		 * @author Simeon Gbolo 04-14-2012
		 * @return the x current x location of this node
		 */
		public int getX()
		{

			return (int) currentXYlocation.getX();
		}

		/**
		 * @return the currentXYlocation
		 */
		public Float getCurrentXYlocation()
		{
			return currentXYlocation;
		}

		/**
		 * @author Simeon Gbolo 04-14-2012
		 * @return the current y location of this node
		 */
		public int getY()
		{

			return (int) currentXYlocation.getY();

		}

		/**
		 * @author Simeon gbolo Used to calculate the slope from one point to
		 *         another This should be called only once before navigating
		 *         from one point to another, This method also sets the new
		 *         starting point for your node's navigation
		 */
		public void getSlope()
		{
			rise = (float) (currentXYdestination.getY() - currentXYlocation
					.getY());
			run = (float) (currentXYdestination.getX() - currentXYlocation
					.getX());
			startingPoint.setLocation(currentXYlocation);
		}

		/**
		 * @author Simeon gbolo This method sets up the math needed to navigate
		 *         from one point to another with a given delta time
		 */
		public void setUpForNavigation(Float new_destination_point)
		{
			startingPoint.setLocation(currentXYlocation);
			currentXYdestination.setLocation(new_destination_point);
			getSlope();
			runningTime = 0;
			state = RedBlackNodeState.moving;

		}

		/**
		 * @author simeon gbolo
		 * @param path
		 *            the path to set
		 */
		public void setPath(Queue<Float> path)
		{
			this.path = path;
			if (!this.path.isEmpty())
			{
				setUpForNavigation(this.path.poll());
				state = RedBlackNodeState.moving;
			}
		}

	}

	// The current color of the node when changing from
	// red to black or black to red
	private Color color;
	private RedBlackNode<AnyType> header;
	private RedBlackNode<AnyType> nullNode;
	private RedBlackNode<AnyType> nodeToBeDeleted;
	private List<Integer> nodeList = new ArrayList<Integer>();
	
	private static final int BLACK = 1; // BLACK must be 1
	private static final int RED = 0;

	// Used in insert routine and its helpers
	private RedBlackNode<AnyType> current;
	private RedBlackNode<AnyType> parent;
	private RedBlackNode<AnyType> grand;
	private RedBlackNode<AnyType> great;

	// the node location of the tree -simeon gbolo
	private HashMap<RedBlackNode<AnyType>, Rectangle> nodeLocations = null;
	// the sizes of the subtrees - simeon gbolo
	private HashMap<RedBlackNode<AnyType>, Dimension> subtreeSizes = null;
	// space between nodes - simeon gbolo
	private int parent2child = 40, child2child = 30;
	// helpers - simeon gbolo
	private Dimension empty = new Dimension(0, 0);
	private FontMetrics fm = null;

	// holds the output of an insertion or deletion
	private static String output;

	private int size;
}
